package 剑指offer.字符串;

import java.util.ArrayList;
import java.util.List;

/*
给出一段字符串：arabcacfr，它里面最长的不含重复字符的子字符串是：acfr，长度为 4
字符串只含 a~z
 */
public class 第48题最长不含重复字符的子字符串 {

    /*
    解法：滑动窗口
    a  r  a  b  c  a  c  f  r
   p1  p2

   设置两根指针 p1、p2 构建一个窗口
   p2 不断后移，遇到一个字符就与窗口内的比较，若没有重复的则继续后移，计数器累加
   若有重复的，则将 p1 移动到重复的那个字符的后一个，计数器累减

   假设现在 p2 指向了 a：  a  r  a  b  c  a  c  f  r
                         p1    p2
                    则 p1 应该移动到 r：
                    a  r  a  b  c  a  c  f  r
                      p1  p2


    假设现在 p2 又指向了 a：  a  r  a  b  c  a  c  f  r
                              p1           p2
                    则 p1 应该移动到 b：
                    a  r  a  b  c  a  c  f  r
                             p1   p2

     现在的问题只有一个了：怎么查出 p2 指向的数据是否在窗口内
     1. 使用一个长度为 122 的数组
     2. 使用自带的 API
     */
    public static int theLongestSubstringWithoutDuplicateCharacters(String str) {
        if (str == null || str.length() == 0)
            return 0;
        if (str.length() == 1) {
            return 1;
        }
        char[] chars = str.toLowerCase().toCharArray();
        int p1 = 0;
        int p2 = 1;
        // 需要把 p1、p2 指向的字符添加到数组里面构建窗口
        List<Character> window = new ArrayList<>();
        window.add(chars[p1]);
        while (p2 < chars.length - 1 && p2 >= p1) {
            // p2 指向的字符不在窗口里面
            if (!window.contains(chars[p2])) {
                window.add(chars[p2]);
                p2++;
            } else {
                int start = window.indexOf(chars[p2]);
                window = window.subList(start+1, window.size() - 1);// 移除重复的数据
                p1 = p1 + start + 1;
                window.add(chars[p2++]);
            }
        }
        return window.size();
    }


    public static void main(String[] args) {
        System.out.println(theLongestSubstringWithoutDuplicateCharacters("arabcacfr"));
    }
}
